/*
 ============================================================================
 Name        : main.c
 Author      : 
 Version     :
 Copyright   : Your copyright notice
 Description : Mutual exclusion algorithm that use O(log n) RMR's and O(1) barriers
 ============================================================================
 */
//////////////////////////////////////////////////////////////////////////
//CAS
//////////////////////////////////////////////////////////////////////////
#if defined(__linux__) || defined(__linux) || defined(__gnu_linux__)
	//////////////////////////////////////////////////////////////////////////
	//types
	//////////////////////////////////////////////////////////////////////////
	typedef unsigned char      _u8;
	typedef unsigned short     _u16;
	typedef unsigned int       _u32;
	typedef unsigned long long _u64;
	typedef unsigned long long tick_t;
	typedef _u32               ptr_t;
	#define CAS32(_a,_o,_n)         __sync_val_compare_and_swap ((_u32*)_a,(_u32)_o,(_u32)_n)
	#define MB()  __sync_synchronize()
	extern  tick_t RDTICK(void);
	#define RDTICK() \
        ({ tick_t __t; __asm__ __volatile__ ("rdtsc" : "=A" (__t)); __t; })
#elif defined(__sun__) || defined(__sun) || defined(sun)
	#include"sparc_defs_cc_TV.h"
#endif


#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <math.h>
#include <time.h>
#define FREE_LOCK       1024

#define true 1
#define false 0
#define  FREE_NODE -1
#define TICK_IN_SEC 1200000000

typedef struct Queue
{
	unsigned short *elements;
	char           *elementsInQueue;
	unsigned short start;
	unsigned short end;
	unsigned short capacity;
}Queue;

extern  int     notEmpty(volatile Queue* q);
extern  void    enqueue(volatile Queue* q, short element);
extern  int     dequeue(volatile Queue* q);
extern  Queue*  createQueue(short maxElements, size_t shortSize);
extern  void    destructorQueue(volatile Queue* q);

inline int notEmpty(volatile Queue* q)
{
	return (q->start != q->end);
}

inline void enqueue(volatile Queue* q, short element)
{
	if((element != FREE_NODE)&&(q->elementsInQueue[element] == false))
	{
		q->elements[q->end] = element;
		
		q->end++;

		if (q->end == q->capacity)

			q->end=0; 		

		q->elementsInQueue[element] = true;
	}
}

inline int dequeue(volatile Queue* q)
{
	int element = q->elements[q->start];

	q->start++;

	if (q->start == q->capacity)

		q->start = 0;

	q->elementsInQueue[element] = false;

	return element;
}

inline Queue* createQueue(short maxElements, size_t shortSize)
{
	Queue* q;
	q                   = (Queue*)malloc(sizeof(Queue));
	q->capacity         = maxElements + 1;
	q->start            = 0;
	q->end              = 0;
	q->elements         = (unsigned short*) malloc((maxElements + 1) * shortSize);
	q->elementsInQueue  = (char*) malloc(maxElements * sizeof(char));

	int i;
	for(i=0; i<maxElements; i++)
	{
		q->elementsInQueue[i] = false;
	}

	return q;
}


inline void destructorQueue(volatile Queue* q)
{
	free(q->elements);

	free(q->elementsInQueue);

	free((void*)q);

}

typedef struct tState
{
	char enter;
	char wait;
	char  padding[62];
}tState;

typedef struct sharedData
{
	volatile Queue*         q;
	volatile short**        tournament;
	volatile tState*        arrState;
	volatile tick_t         startTime;
	volatile tick_t        finishTime;
	volatile unsigned long int       countVisitInCS;
	volatile unsigned int   lock;
	volatile unsigned int	exits;
	volatile unsigned int   testMutualExclusion;
	volatile unsigned int   startClock;
	unsigned int                     numEnters;
        unsigned short int               maxThreadNum;
	unsigned short int               toursize;
	volatile unsigned char           flagStartClock;
	volatile unsigned char           flag;
}sharedData;

typedef struct thData
{
	sharedData*    sData;
	long int       counter;
	int            id;
        char           padding[54];
}thData;

pthread_barrier_t bar;



void clearVar(sharedData* pSharedData)                     /* Free memory */
{
	int i;

	pthread_barrier_destroy(&bar);

	if (pSharedData->arrState != NULL)
	{
		free((void*)pSharedData->arrState);

		pSharedData->arrState = NULL;
	}

	if (pSharedData->tournament != NULL)
	{

		for(i=0; i<pSharedData->toursize; i++)
		{
			free((void*)pSharedData->tournament[i]);

			pSharedData->tournament[i] = NULL;
		}

		free(pSharedData->tournament);

		pSharedData->tournament = NULL;
	}

	if(pSharedData->q != NULL)
	{
		destructorQueue(pSharedData->q);

		pSharedData->q = NULL;
	}

	free(pSharedData);

	pSharedData = NULL;
}

void test(thData* data)                                    // Test that only one process exist in critical section
{
	if(CAS32(&data->sData->testMutualExclusion, FREE_LOCK, data->id) != FREE_LOCK)
	{
		printf("\nError, mutual exclusion fail.\n");
	}
}

void test1(thData* data)
{
	CAS32(&data->sData->testMutualExclusion, data->id, FREE_LOCK);

}


void* threadRunAlgo(void* ptr)                             // Algorithm for mutual exclusion
{
	int j;

	unsigned int t, e;

	int thread;

	thData*              pThData   = (thData*)ptr;
	sharedData*          sData     = pThData->sData;
	volatile short**     tour      = sData->tournament;
	volatile Queue*      q         = sData->q;
	volatile tState*     arrState  = sData->arrState;
	volatile char*      tEnter    = &arrState[pThData->id].enter;
	volatile char*      tWait     = &arrState[pThData->id].wait;


	/************** All thread start to run together ******************/

	pthread_barrier_wait(&bar);                        // Marked as comment when single process run alone
        
	if (CAS32(&sData->startClock, FREE_LOCK, 0) == FREE_LOCK) //Start time measuring
	{
		sData->startTime = RDTICK();
		sData->flagStartClock = false;
		MB();
	}

	while(sData->flagStartClock)
	{}

	while(sData->flag)
	{

		/************** Entry code ****************************************/

		*tEnter= true;

		int node       = pThData->id;



		/*up hill*/
		for(j=0; j< sData->toursize; j++  )
		{
			tour[j][node] = pThData->id;
			node >>= 1;
		}

		MB();

		t = CAS32(&sData->lock, FREE_LOCK, pThData->id);

		if (t != FREE_LOCK)
		{

			e = sData->exits;

			while((sData->exits - e < 2) && (sData->lock != pThData->id) && (sData->lock != FREE_LOCK))
			{}

			if(CAS32(&sData->lock, FREE_LOCK, pThData->id) != FREE_LOCK)
			{

				while(*tWait){}

			}

		}

		/************** Critical section *******************************/

		 sData->countVisitInCS++;

		 pThData->counter++;

		 if(sData->countVisitInCS == sData->numEnters)
		 {
			 //Stop time measuring
			 sData->finishTime = RDTICK();
			 sData->flag = 0;
			 MB();

		 }

		/************** Exit code **************************************/

		*tEnter = false;

		sData->exits = sData->exits + 1;

		*tWait  = true;

		/* down hill */

		thread = tour[sData->toursize - 1][0];

		if ((thread != FREE_NODE) && (thread != pThData->id) && arrState[thread].enter)
			 enqueue(q, thread);

		for(j=sData->toursize - 2; j>=0; j--  )
		{

			node = pThData->id >>j ;

			if(node & 1)
			{
				node -= 1;
			}

			thread = tour[j][node];


			if ((thread != FREE_NODE) && (thread != pThData->id)  && arrState[thread].enter)
			{
				enqueue(q, thread);
			}

			thread = tour[j][node + 1];

			if ((thread != FREE_NODE) && (thread != pThData->id)  && arrState[thread].enter)
			{
				enqueue(q, thread);
			}

		}

//		test1(pThData);

		if (notEmpty(q))
		{

			thread = dequeue(q);

			sData->lock = thread;

			MB();

			arrState[thread].wait = false;
		}

		else
		{
			sData->lock = FREE_LOCK;
		}

		MB();

	}

//	printf("%ld ",pThData->counter);

	if (pThData->id < sData->maxThreadNum -1)
	{
		pthread_exit(NULL);
	}

	return NULL;
}

void* threadWrite(void* ptr) //creating RMR's
{
	int j;

	thData*              pThData   = (thData*)ptr;
	sharedData*          sData     = pThData->sData;
	volatile short**     tour      = sData->tournament;

	while(sData->flag)
	{

		int node       = sData->maxThreadNum - 1;

		/*up hill*/
		for(j=0; j< sData->toursize; j++  )
		{
			tour[j][node] = FREE_NODE;
			node >>= 1;
		}

	}

	if (pThData->id < sData->maxThreadNum -1)
	{
		pthread_exit(NULL);
	}

	return NULL;
}

sharedData* initalizeVar(int argc,char* argv[])       // Memory allocating and Initialize Data structures
{

	int i,j, levelSize;

	size_t shortSize = sizeof(short);

	sharedData* pSharedData = (sharedData*)malloc(sizeof(sharedData));

	pSharedData->maxThreadNum = 0;

	pSharedData->numEnters    = 0;

	pSharedData->arrState     = NULL;

	pSharedData->tournament   = NULL;

	pSharedData->q            = NULL;

	if ( argc == 4 )
	{

		pSharedData->maxThreadNum = atoi(argv[2]);

		pSharedData->numEnters    = atoi(argv[3]);


		if (pSharedData->maxThreadNum < 1)
		{
			 printf("0 processes\n");
			 return NULL;
		}

		freopen (*++argv,"a",stdout);
	}

	printf("Algorithm ");

	pSharedData->arrState  = (tState*)malloc(pSharedData->maxThreadNum * sizeof(tState));

	for (i=0; i<pSharedData->maxThreadNum; i++)
	{
		pSharedData->arrState[i].enter = false;

		pSharedData->arrState[i].wait  = true;

	}

	pSharedData->toursize = ceil(log2(pSharedData->maxThreadNum)) + 1;

	pSharedData->tournament = (volatile short**)malloc(pSharedData->toursize * sizeof(volatile short*));

	levelSize = pow(2, ceil(log2(pSharedData->maxThreadNum)));

	for(i=0; i<pSharedData->toursize; i++)
	{
		pSharedData->tournament[i] = (short*)malloc(levelSize * shortSize);


		for(j=0; j<levelSize; j++)
		{
			pSharedData->tournament[i][j] = FREE_NODE;
		}

		levelSize     /= 2;
	}

	pSharedData->q = createQueue(pSharedData->maxThreadNum, shortSize);

	pthread_barrier_init(&bar, NULL, pSharedData->maxThreadNum);

	pSharedData->exits = 0;

	pSharedData->lock = FREE_LOCK;

	pSharedData->testMutualExclusion = FREE_LOCK;

	pSharedData->countVisitInCS = 0;

	pSharedData->flag = 1;

	pSharedData->flagStartClock = 1;

	pSharedData->startClock = FREE_LOCK;

	return pSharedData;
}


int main(int argc, char *argv[]) {

	int i;

	tick_t time;

	sharedData* pSharedData = initalizeVar(argc, argv);

	pthread_t*  threads     = (pthread_t*) malloc((pSharedData->maxThreadNum -1)* sizeof(pthread_t));

	thData*     tData       = (thData*)malloc(pSharedData->maxThreadNum * sizeof(thData));



	for(i=0; i<pSharedData->maxThreadNum ; i++)
	{
		tData[i].id        = i;
		tData[i].counter   = 0;
		tData[i].sData     = pSharedData;
		if(i <pSharedData->maxThreadNum - 1)                     // Marked as comments when single process run alone
		{
			pthread_create(&threads[i], NULL, threadRunAlgo, &tData[i]);
		}
	}

//	pthread_create(&threads[0], NULL, threadWrite, &tData[0]);      // Create process who cause RMRS in single process run

	threadRunAlgo(&tData[pSharedData->maxThreadNum - 1]);

//	pthread_join(threads[0] , NULL);                                // Wait for process who cause RMR's to finish.

	for(i=0; i<pSharedData->maxThreadNum - 1; i++)                  // Marked as comment when single process run alone
	{
		pthread_join(threads[i] , NULL);
	}


	time = pSharedData->finishTime - pSharedData->startTime;

	printf("%d %d %llu\n", pSharedData->maxThreadNum, pSharedData->numEnters,time);

	clearVar(pSharedData);

	free(threads);

	free(tData);

	fclose(stdout);


	return EXIT_SUCCESS;
}


